import java.util.Random;

class Solution {
    // public int findKthLargest(int[] nums, int k) {
    //     // 不讲武德的解法：内置函数排序+查找
    //     Arrays.sort(nums);
    //     return nums[nums.length - k];
    // }

    // public int findKthLargest(int[] nums, int k) {
    //     // 使用 堆排序
    //     // 默认是小根堆，但题目是要求第k个最大的元素
    //     // lambda表达式也可以使用更加简洁的写法：(a, b) -> b - a
    //     PriorityQueue<Integer> queue = new PriorityQueue<>((a, b)->b.compareTo(a));
    //     for (int x : nums) {
    //         queue.offer(x);
    //     }
    //     // 再从队列中出k个元素即可
    //     int ret = 0;
    //     for (int i = 0; i < k; i++) {
    //         ret = queue.poll();
    //     }
    //     return ret;
    // }

    public int findKthLargest(int[] nums, int k) {
        // 使用快速选择算法
        // 首先得使用数组分三块的操作，将数组划分，然后再去判断
        return quick_sort(nums, 0, nums.length-1, k);
    }

    private int quick_sort(int[] nums, int start, int end, int k) {
        // 递归的结束条件之一
        if (start == end) {
            return nums[start];
        }
        // 随机选择一个基准元素
        int key = nums[new Random().nextInt(end-start+1)+start];
        // 根据基准元素将数组分为三块
        int left = start-1, right = end+1;
        for (int i = start; i != right;) {
            if (nums[i] < key) {
                swap(nums, ++left, i++);
            } else if (nums[i] > key) {
                swap(nums, --right, i);
            } else {
                i++;
            }
        }
        // [start, left]、[left+1, right-1]、[right, end]
        // 根据 k 与 分块的数组大小来决定接下来怎么走
        int c = end-right+1, b = right-1-left;
        if (k <= c) { // 说明 k 对应的值 在 c 中
            return quick_sort(nums, right, end, k);
        } else if (k <= b+c) { // 说明 k 对应的值在 b 中
            return key;
        } else { // 说明 k 对应的值在 a 中
            return quick_sort(nums, start, left, k-b-c);
        }
    }

    private int quick_sort2(int[] nums, int start, int end, int k) {
        // 递归结束的条件之一
        if (start == end) {
            return nums[start];
        }
        int key = nums[new Random().nextInt(end-start+1)+start];
        int left = start-1, right = end+1;
        for (int i = start; i != right;) {
            int j = nums[i];
            if (j < key) {
                swap(nums, ++left, i++);
            } else if (j > key) {
                swap(nums, --right, i);
            } else {
                i++;
            }
        }
        // 经过上面的处理，数组已经分为了三块，接下来得根据k的值来决定怎么走了
        if (end - right + 1 >= k) {
            return quick_sort2(nums, right, end, k);
        } else if (end - left >= k) {
            return key;
        } else {
            return quick_sort2(nums, start, left, k-(end-left));
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}